package com.lw.leetcode.bit.c;

import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * 1755. 最接近目标值的子序列和
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/16 15:55
 */
public class MinAbsDifference {

    public static void main(String[] args) {
        MinAbsDifference test = new MinAbsDifference();

        // 0
        int[] nums = {5, -7, 3, 5};
        int goal = 6;

        // 1
//        int[] nums = {7, -9, 15, -2};
//        int goal = -5;

        // 7
//        int[] nums = {1, 2, 3};
//        int goal = -7;

        int i = test.minAbsDifference(nums, goal);
        System.out.println(i);

    }


    private int goal;

    public int minAbsDifference(int[] nums, int goal) {
        this.goal = goal;
        int length = nums.length;
        int m = (length + 1) >> 1;
        int size = (1 << m);
        int[] arr = new int[size];
        TreeSet<Integer> set = find(nums, arr);
        System.out.println(set);
        int n = (1 << (length - m));
        int min = Math.min( getMin(set, 0), Math.abs(goal));
        for (int i = 1; i < n; i++) {
            int t = i & (i - 1);
            int v = arr[t] + nums[Integer.bitCount(i - t - 1) + m];
            min = Math.min(min, getMin(set, v));
            arr[i] = v;
        }
        return min;
    }

    private int getMin(TreeSet<Integer> set, int v) {
        int t = goal - v;
        Integer r = set.floor(t);
        int min = Integer.MAX_VALUE;
        r = r == null ? 0 : r;
        min = Math.min(min, Math.abs(goal - (v + r)));
        r = set.ceiling(t);
        r = r == null ? 0 : r;
        min = Math.min(min, Math.abs(goal - (v + r)));
//        System.out.println(v + "   " + min);
        return min;
    }

    private TreeSet<Integer> find(int[] nums, int[] arr) {
        int length = arr.length;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 1; i < length; i++) {
            int t = i & (i - 1);
            arr[i] = arr[t] + nums[Integer.bitCount(i - t - 1)];
            set.add(arr[i]);
        }
        return set;
    }

}
